﻿#include "unit_test.h"
#include <stack>
#include <cassert>

namespace code_01_01
{
    /**
     * 最小元素栈
     */
    class MinStack
    {
    public:
        void push(int i)
        {
            elements_.push(i);
            if (min_.empty() || i <= min_.top())
            {
                min_.push(i);
            }
        }

        int pop()
        {
            assert(!elements_.empty());
            int result = elements_.top();
            elements_.pop();
            if (result == min_.top())
            {
                min_.pop();
            }
            return result;
        }

        int getMin() const
        {
            assert(!min_.empty());
            return min_.top();
        }

    private:
        std::stack<int> elements_;
        std::stack<int> min_;
    };

    TEST(MinStack)
    {
        MinStack stack;

        // push 1 2 1 0
        stack.push(1);
        ASSERT_EQ(1, stack.getMin());
        stack.push(2);
        ASSERT_EQ(1, stack.getMin());
        stack.push(1);
        ASSERT_EQ(1, stack.getMin());
        stack.push(0);
        ASSERT_EQ(0, stack.getMin());

        // pop 0 1 2 1
        ASSERT_EQ(0, stack.pop());
        ASSERT_EQ(1, stack.getMin());
        ASSERT_EQ(1, stack.pop());
        ASSERT_EQ(1, stack.getMin());
        ASSERT_EQ(2, stack.pop());
        ASSERT_EQ(1, stack.getMin());
        ASSERT_EQ(1, stack.pop());
    }
}
